package main

import (
	"fmt"
	. "go_data_structures_and_algorithms/system_class/section10/pojo"
)

func main() {
	node1 := &RandomListNode{
		Label:  1,
		Next:   nil,
		Random: nil,
	}
	node2 := &RandomListNode{
		Label:  2,
		Next:   nil,
		Random: nil,
	}
	node3 := &RandomListNode{
		Label:  3,
		Next:   nil,
		Random: nil,
	}
	node4 := &RandomListNode{
		Label:  3,
		Next:   nil,
		Random: nil,
	}
	node5 := &RandomListNode{
		Label:  2,
		Next:   nil,
		Random: nil,
	}
	node6 := &RandomListNode{
		Label:  1,
		Next:   nil,
		Random: nil,
	}

	node1.Next = node2
	node2.Next = node3
	node3.Next = node4
	node4.Next = node5
	node5.Next = node6

	clone := Clone(node1)

	for clone != nil {
		fmt.Println(clone.Label)
		clone = clone.Next

	}
}

func Clone(head *RandomListNode) *RandomListNode {
	if head == nil {
		return nil

	}
	//1.创建每个节点的影子节点也就是直接插入在每个节点的之后
	cur1 := head

	for cur1 != nil {
		next := cur1.Next
		cloneNode := &RandomListNode{
			Label:  cur1.Label,
			Next:   nil,
			Random: nil,
		}

		cur1.Next = cloneNode
		cloneNode.Next = next
		cur1 = next

	}

	//2.遍历链表让影子节点的random赋值对应的节点 ，稍微想想就好
	cur2 := head
	for cur2 != nil {
		if cur2.Random != nil {
			cur2.Next.Random = cur2.Random.Next
		}
		cur2 = cur2.Next.Next
	}

	//3.分隔影子指针 遍历节点让head隔一个连接组成原来的链表的同时创建一个新的链表头指针并赋值影子节点的头一个节点
	//之后他用来连接隔着一个的影子节点稍微想一下步骤很容易出来的不再过多赘述
	cur3 := head
	var cloneHead *RandomListNode
	cloneHead = cur3.Next
	cloneHeadBack := cloneHead
	cur3.Next = cur3.Next.Next
	cur3 = cur3.Next
	for cur3 != nil {
		cloneHeadBack.Next = cur3.Next
		cloneHeadBack = cloneHeadBack.Next
		cur3.Next = cur3.Next.Next
		cur3 = cur3.Next
	}

	return cloneHead
}
